package exercises.leetcode;

import java.util.PriorityQueue;

/**
 * <a href="https://leetcode-cn.com/problems/smallest-k-lcci/">
 * 面试题 17.14. 最小K个数</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 * <p>
 * 示例：
 * <p>
 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出： [1,2,3,4]
 * <p>
 * 提示：
 * <p>
 * 0 <= len(arr) <= 100000
 * 0 <= k <= min(100000, len(arr))
 *
 * @author or2
 * @date 2021年09月25日 时间: 20:24
 */
public class Interview17th14 {
    /**
     * 使用 堆排序-优先队列进行的尝试
     *
     * @param arr 原数组
     * @param k   所需的数组中最小的k个数
     * @return 最小数的个数
     */
    public int[] smallestK(int[] arr, int k) {
        /*校验输入*/
        if (k == 0)
            return new int[0];
        if (arr.length < k)
            return arr;

        /*使用优先队列(有序队列, 且不必全部有序)*/
        PriorityQueue<Integer> heap = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);
        for (int i = 0; i < k; i++)
            heap.add(arr[i]);
        for (int i = k; i < arr.length; i++)
            if (heap.peek() > arr[i]) {
                heap.poll();
                heap.add(arr[i]);
            }

        /*避免获取heap元素时, 数据结构为了维持平衡所作的上升下沉*/
        Integer[] ints = new Integer[k];
        heap.toArray(ints);
        int[] ans = new int[k];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = ints[i];
        }
        return ans;
    }

//———————————————————— 大顶堆 - 改进② ——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

    /**
     * 使用自己定义的 大顶堆
     */
    public int[] smallestKWithCustom(int[] arr, int k) {
        /*校验输入*/
        if (k == 0)
            return new int[0];
        if (arr.length < k)
            return arr;

        /*使用优先队列(有序队列, 且不必全部有序)*/
        int[] ans = new int[k];
        Heap heap = new Heap(ans);
        for (int i = 0; i < k; i++)
            heap.add(arr[i]);
        for (int i = k; i < arr.length; i++)
            if (ans[0] > arr[i])
                heap.replaceFirst(arr[i]);

        /*避免获取heap元素时, 数据结构为了维持平衡所作的上升下沉*/
        return ans;
    }

    /**
     * 自定义 - 大顶堆
     */
    public static class Heap {
        int[] arr;
        private int size;

        public Heap(int[] arr) {
            this.arr = arr;
            size = 0;
        }

        public void add(int value) {
            int k = size;
            arr[size++] = value;

            int parent = parent(k);
            while (k > 0 && arr[parent] < arr[k]) {
                swap(k, parent);
                k = parent(k);
                parent = parent(k);
            }
        }

        /**
         * 使用下沉, 直接替换第一个元素
         *
         * @param value 新插入的元素
         */
        public void replaceFirst(int value) {
            arr[0] = value;
            int length = arr.length;

            int k = 0;
            while (leftChild(k) < length) {
                int j = leftChild(k);
                /*若其也有右孩子, 选择较大的一个*/
                if (j + 1 < length && arr[j + 1] > arr[j])
                    j++;

                if (arr[k] >= arr[j])
                    break;

                swap(k, j);
                k = j;
            }
        }

        private void swap(int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        private int parent(int index) {
            return index - 1 >> 1;
        }

        private int leftChild(int index) {
            return (index << 1) + 1;
        }
    }

//———————————————————— 大顶堆 - 改进③ ——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

    /**
     * 将所有函数内联
     */
    public int[] smallestKAllCustom(int[] arr, int k) {
        /*校验输入*/
        if (k == 0)
            return new int[0];
        int length = arr.length;
        if (length < k)
            return arr;

        /*使用优先队列(有序队列, 且不必全部有序)*/
        int[] ans = new int[k];
        for (int i = 0, index; i < k; i++) {
            index = i;
            ans[i] = arr[i];

            /*寻找父亲结点*/
            int parent = i - 1 >> 1;
            while (index > 0 && ans[parent] < ans[index]) {
                /*交换节点*/
                ans[index] ^= ans[parent];
                ans[parent] ^= ans[index];
                ans[index] ^= ans[parent];
                index = index - 1 >> 1;
                parent = index - 1 >> 1;
            }
        }
        for (int i = k; i < length; i++)
            if (ans[0] > arr[i]) {
                ans[0] = arr[i];

                int index = 0;
                /*判断左孩子大小, 决定是否下沉*/
                while ((index << 1) + 1 < k) {
                    int j = (index << 1) + 1;
                    /*若其也有右孩子, 选择较大的一个*/
                    if (j + 1 < k && ans[j + 1] > ans[j])
                        j++;

                    if (ans[index] >= ans[j])
                        break;

                    /*交换结点*/
                    ans[index] ^= ans[j];
                    ans[j] ^= ans[index];
                    ans[index] ^= ans[j];
                    index = j;
                }
            }

        return ans;
    }

//———————————————————— 快速排序 ——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

    private int bound;

    /**
     * 使用快速排序解决
     */
    public int[] quickSort(int[] arr, int k) {
        /*校验输入*/
        if (arr.length == 0)
            return arr;
        bound = k;
        quickSort(arr, 0, arr.length);
        int[] ans = new int[k];
        System.arraycopy(arr, 0, ans, 0, k);
        /*帮助gc*/
        arr = null;
        System.gc();
        return ans;
    }

    /**
     * 对 arr 数组的 [start, end) 区间进行快速排序
     *
     * @param arr   被排序的数组
     * @param start 开始排序的下标
     * @param end   终止的下标(不包含该下标)
     */
    public void quickSort(int[] arr, int start, int end) {
        /*随机选定标定点(但是会明显影响效率)*/
        int beacon = arr[start + (int) ((end - start) * Math.random())];

        /*划分*/
        int lt = start, gt = end, eq = lt;
        while (eq < gt) {
            if (arr[eq] == beacon) eq++;
            else if (arr[eq] < beacon) swap(arr, lt++, eq++);
            else swap(arr, eq, --gt);
        }

        /*解决子问题 + 剪枝*/
        if (start < lt - 1 && start > bound)
            quickSort(arr, start, lt);
        if (gt < end - 1 && gt < bound)
            quickSort(arr, gt, end);
    }

    private void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}
